Convex Optimization 2015.09.23

Positive (semi)definite metrics

  • Notations: A∈Sn means A∈Rn×n, A symmetric

    A≥0 or A∈Sn+ means A positive semidefinite (xTAx≥0,∀x∈Rn)

    A>0 or A∈Sn++ means A positive definite (xTAx>0,∀x∈Rn∖{0})

  • Reminder: A matrix A is symmetric iff it is orthogonally diagonalizable: A=PTDP,PP=I

  • Facts: A≥0⟺D≥0⟺ all eigenvalues of A are nonnegative

    A>0⟺D>0⟺ all eigenvalues of A are positive

  • Proof: If D≥0, then ∃D′≥0,s.t.D=D′2

    Then xTAx=xTPTD′D′Px=(D′Px)TD′Px=‖D′Px‖22≥0

  • Notations: Outer product (of x,y): xyT=[x][y]=[x1y1⋯x1yn⋮⋮xny1⋯xnyn]

    Let A=[aT1⋯aTn]T, B=[b1...bn]

    Then BA=[b1⋯bn][aT1⋮aTn]=b1aT1+...+bnaTn

  • Lemma: If A≥0 and Aii=0, then the ith row and column of A are zero.

  • Picture:

    [0000000]

  • Proof: WLOG i=1, If A1j≠0, then let x=→e1+λ→ej.

    Then xTAx=λ2Ajj+2λA1j

    ddλxTAx=λ≠0(2λAjj+2A1j)|λ=0=2A1j≠0,(xTAx)|λ=0=0

  • Lemma: Any matrix of the form BTB is positive semidefinite, B∈Rm×n

  • Proof: Trivial (xTBTBx=‖Bx‖22)

  • Fact: For every A∈Sn+ there exists B∈Rn×n, B upper triangle, such that A=BTB (Cholesky decomposition)

    $B^TB =

    [||||||||||][−−−−−−−−−−]

    = A = $

    $

    [||||][−−−−]
    • [|||][−−−]
      • = $
      [∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗]+[∗∗∗∗∗∗∗∗∗]+...+[∗]

  • Proof: By lemma, can assume A11≠0, in fact, can assume that A11=1, So

    A=[1aT12a12A22],B=[1aT12−−−−−−]

    [1a12][1aT12]=[1aT12a12a12aT12]

    Have A−[1a12][1aT12]=[000A22−a12aT12]

    So need to show that:

    S=A22−a12aT12∈Sn−1+ is positive semidefinite

    Let x∈Rn−1,

    Then xTSx=xTAx−xTa12aT12x=xTA−(aT12x)2

    Let y=[−aT12xx],

    yTAy=(aT12x)2+xTA22x−(aT12x)2−(aT12x)2=xTSx≥0

  • Basic Fact: x→√xTAx is a norm if A>0

  • Proof: ‖x+y‖≤‖x‖+‖y‖

    √(x+y)TA(x+y)≤√xTAx+√yTAy

    xTAx+yTAy+2xTAy≤xTAx+yTAy+2√xTAx√yTAy

    (yATx)(yATx)≤(xTAx)(yTAy)

    Let z=Bx,w=By,

    Then (wTz)(wTz)≤(zTz)(wTw)=‖z‖22‖w‖22

  • Basic Fact: The function x→xTAx is convex if A≥0

  • Proof: Same as for the function x2 (At some point use that (x+y)TA(x+y)≥0)

  • Definition: An ellipsod in Rn is a set of the form E={x:(x−x0)TA−1(x−x0)≤1}

    for some A>0

    Have A=PTDP, put x−x0=PTu

    A−1=PTD−1P,(uTP)A−1(PTu)=uTD−1u=∑ni=11λiu2i

  • Lemma: A set E is an ellipsoid iff and only if there exists an invertible matrix Z∈Rn×n,s.t.E={x0+Zu:‖u‖2≤1}

  • Proof: {x0+Zu:‖u‖2≤1}={y:‖Z−1(y−x0)‖2≤1}={y:(y−x0)TZ−1TZ−1(y−x0)≤1}

Hyperplane Seperation Theorem:

  • Theorem: If C,D∈Rn are convex sets, disjoint, then there exists a∈Rn∖0,b∈R,s.t.aTx≤b,∀x∈C;aTx≥b,∀x∈D

  • Proof: when C,D are closed and D is bonded,

    Let d(C,D)=infx∈C,y∈D‖x−y‖2,

    Then ∃(xn)∞n=1⊆C,(yn)∞n=1⊆D,s.t.limn→∞‖xn−yn‖2=d(C,D)

    Even, can assume (yn)∞n=1 is convergent.

    Then limn→∞yn∈D because D is closed

    can also assume that xn convergent

    Now, let c=limn→∞xn∈C,d=limn→∞yn∈D

    Then ‖c−d‖2=limn→∞‖xn−yn‖2=d(C,D)>0

    Choose a=d−c,b=(d−c)T(d+c2)

    Assume by contradiction that ∃x0∈D,s.t.aTx0<b

    Hope is that some point of form d+λ(x0−d) is even closer to c than d is,

    for λ∈[0,1],(d+λ(x0−d)−c)T(d+λ(x0−d)−c)

    =dTd−2dTc+cTc+2λ(x0−d)T(d−c)+λ2(x0−d)T(x0−d)

    =‖d−c‖22+2λ(x0−d)T(d−c)+λ2(x0−d)T(x0−d)

    And (d−c)T(d−c2)=‖d−c‖222≥0,aTx0<b

    ⟹(x0−d)T−(d−c)T(d+c2)<0

    So (x0−d)T−(d−c)T(d+c2)−(d−c)T(d−c2)<0

    ⟹λ=0,ddλ⋯=(x0−d)T(d−c)+2λ(x0−d)T(x0−d)=(x0−d)T(d−c)<0

    min‖Ax−b‖22 where A∈Rm×n,b∈Rm

    Have ‖Ax−b‖22=(Ax−b)T(Ax−b)=xTATAx−2bTAx+bTb

  • Definition: ∇f(x1,⋯,xn)=[∂∂x1f,...,∂∂xnf]T

    ∇bTb=0,∇−2bTAx=−2ATb,∇xTATAx=2ATAx(ATAx−ATb=0)